package com.tys.algorithm.advanced.test.class43;

// leetcode 464题
public class Code01_CanIWin {

    // 1~choose 拥有的数字
    // total 一开始的剩余
    // 返回先手会不会赢
    public static boolean canIWin0(int choose, int total) {
        //规定total为0，先手赢，返回true
        if (total == 0) {
            return true;
        }
        //所有数字 < total 怎么减也不可能为0：choose=10, total=100
        //返回false
        if ((choose * (choose + 1) >> 1) < total) {
            return false;
        }
        //生成数组：1-choose
        int[] arr = new int[choose];
        for (int i = 0; i < choose; i++) {
            arr[i] = i + 1;
        }
        // arr[i] != -1 表示arr[i]这个数字还没被拿走
        // arr[i] == -1 表示arr[i]这个数字已经被拿走
        // 集合，arr，1~choose
        return process(arr, total);
    }

    // 当前轮到先手拿，
    // arr: 先手只能选择在arr中还存在的数字，
    // rest: 还剩rest这么值，
    // 返回先手会不会赢
    public static boolean process(int[] arr, int rest) {
        if (rest <= 0) {
            //先手输了，没有可选的了
            return false;
        }
        // 先手去尝试所有的情况
        for (int i = 0; i < arr.length; i++) {
            //当前位置有数
            if (arr[i] != -1) {
                //先手拿当前数
                int cur = arr[i];
                //设置为无效
                arr[i] = -1;
                //子过程的后手赢了，就是当前先手赢了
                boolean next = process(arr, rest - cur);
                //恢复原始值
                arr[i] = cur;
                if (!next) {
                    return true;
                }
            }
        }
        return false;
    }

    // 这个是暴力尝试，思路是正确的，超时而已
    public static boolean canIWin1(int choose, int total) {
        if (total == 0) {
            return true;
        }
        if ((choose * (choose + 1) >> 1) < total) {
            return false;
        }
        return process1(choose, 0, total);
    }

    // 当前轮到先手拿，
    // 先手可以拿1~choose中的任何一个数字
    // status   i位如果为0，代表没拿，当前可以拿
    //          i位为1，代表已经拿过了，当前不能拿
    // 还剩rest这么值，
    // 返回先手会不会赢
    // choose固定，status,rest可变，动态规划，记忆化搜索
    public static boolean process1(int choose, int status, int rest) {
        if (rest <= 0) {
            return false;
        }
        //在1-choose范围
        for (int i = 1; i <= choose; i++) {
            // i 这个数字，是此时先手的决定！
            // 看i位置是否为0，即没有拿
            if (((1 << i) & status) == 0) {
                //设置status的i位为1：status | (1 << i)
                if (!process1(choose, (status | (1 << i)), rest - i)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 暴力尝试改动态规划而已
    public static boolean canIWin2(int choose, int total) {
        if (total == 0) {
            return true;
        }
        if ((choose * (choose + 1) >> 1) < total) {
            return false;
        }
        //准备动态规划表:0位置不用，从1开始
        int[] dp = new int[1 << (choose + 1)];
        // dp[status] == 1  true 算过结果true
        // dp[status] == -1  false 算过结果flase
        // dp[status] == 0  process(status) 没算过！去算！
        return process2(choose, 0, total, dp);
    }

    // 为什么明明status和rest是两个可变参数，
    // 却只用status来代表状态(也就是dp)
    // 因为选了一批数字之后，得到的和一定是一样的，
    // 所以rest是由status决定的，所以rest不需要参与记忆化搜索
    public static boolean process2(int choose, int status, int rest, int[] dp) {
        //算过命中缓存
        if (dp[status] != 0) {
            return dp[status] == 1 ? true : false;
        }
        //没算过，计算
        boolean ans = false;
        if (rest > 0) {
            for (int i = 1; i <= choose; i++) {
                if (((1 << i) & status) == 0) {
                    if (!process2(choose, (status | (1 << i)), rest - i, dp)) {
                        ans = true;
                        break;
                    }
                }
            }
        }
        //放入缓存
        dp[status] = ans ? 1 : -1;
        return ans;
    }

}
